package com.cdream.basic.algorithm.leetcode.dfs;

/**
 * @author cdream
 * @date 2022/2/12
 */
public class Question1020 {
    public static int[][] dirs = new int[][]{{0,1},{1,0},{0,-1},{-1,0}};
    public boolean[][] used;
    public int numEnclaves(int[][] grid) {
        used = new boolean[grid.length][grid[0].length];
        // 遍历每个单元格，然后上下左右移动，一旦遇到边界陆地记录为2，统计2的数量
        for(int m=0; m<grid.length;m++){
            dfs(grid,m,0);
            dfs(grid,m,grid[0].length-1);
        }
        for(int n=1; n<grid[0].length-1;n++){
            dfs(grid,0,n);
            dfs(grid,grid.length-1,n);
        }
        int res = 0;
        for(int i = 1; i<grid.length-1;i++){
            for(int j = 1; j<grid[0].length-1;j++){
                if(!used[i][j] && grid[i][j]==1){
                    res++;
                }
            }
        }
        return res;
    }
    void dfs(int[][] grid,int m,int n){
        if(m<0 || n<0 || m>=grid.length || n>=grid[0].length || grid[m][n]==0 || used[m][n]){
            return;
        }
        used[m][n] = true;
        for(int[] dir: dirs){
            dfs(grid,m+dir[0],n+dir[1]);
        }
    }

    public static void main(String[] args) {
        new Question1020().numEnclaves(new int[][]{{0,1,1,0},{0,0,1,0},{0,0,1,0},{0,0,0,0}});
    }
}
